Fast extrapolation from ⟨ω⟩

Given $P ∈ \F[X]$ with $\deg P < n$ and $ω$ a $n$-primitive root of unity. Evaluate $P$ on the subgroup generated by $ω$:

$$ a_i = P(ω^i) $$

Goal. Given only $a_i$ and arbitrary $z ∈ \F$, efficiently evaluate $P(z)$.


Observe the Lagrange basis for $⟨ω⟩$:

$$ L_i(X) = c_i \frac{X^n - 1}{X-ω^i} $$

where $c_i$ is set such that $L_i(ω^j) = \delta_{ij}$ (i.e. one when $i = j$ and zero otherwise). Using L'Hospital rule we find:

$$ \left. \frac{X^n - 1}{X-\omega^i} \right\vert_{X=ω^i} = \left. \frac{n⋅X^{n-1}}{1} \right\vert_{X=ω^i} = n ⋅ ω^{i(n-1)} = \frac{n}{ω^i} $$

and thus

$$ L_i(X) = \frac{\omega^i}{n} \frac{X^n - 1}{X-\omega^i} $$


$$ \begin{aligned} P(z) &= \sum_i a_i ⋅ L_i(z) \\&= \sum_i a_i ⋅ \frac{\omega^i}{n} \frac{z^n - 1}{z - \omega^i} \\&= \frac{z^n - 1}{n} \sum_i \frac{a_i ⋅ \omega^i}{z - \omega^i} \end{aligned} $$

This can be evaluated in $\mathcal{O}(1)$ space and $\mathcal{O}(m + \log n)$ time, where $m$ is the number of non-zero entries in $\vec a$.

Remco Bloemen
Math & Engineering
https://2π.com